/* 435. 无重叠区间 */
/**
 * @param {number[][]} intervals
 * @return {number}
 */

/* 测试不通过 */
var eraseOverlapIntervals = function (intervals) {
	if (!intervals.length) return 0
	intervals.sort((a, b) => a[0] - b[0])
	const n = intervals.length
	/* 索引i 需要被移除的最大数目 */
	const f = new Array(n).fill(1)

	for (let i = 1; i < n; i++) {
		for (let j = 0; j < i; j++) {
			if (intervals[j][1] <= intervals[i][0]) {
				f[i] = Math.max(f[i], f[j] + 1)
			}
		}
	}

	return n - Math.max(...f)
}
// 贪心
var eraseOverlapIntervals = function (intervals) {
	const n = intervals.length
	if (!n) return 0
	intervals.sort((a, b) => a[1] - b[1])

	let right = intervals[0][1]
	let ans = 1
	for (let i = 1; i < n; ++i) {
		if (intervals[i][0] >= right) {
			++ans
			right = intervals[i][1]
		}
	}

	return n - ans
}
const ret = eraseOverlapIntervals([
	[1, 100],
	[11, 22],
	[1, 11],
	[2, 12],
])
console.log('eraseOverlapIntervals :>>', ret)
